package ch.ethz.fcl.metrobuzz.algorithm.voronoi.Okabe;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

import ch.ethz.fcl.metrobuzz.spatialindex.object2d.Point2D;
import ch.ethz.fcl.metrobuzz.spatialindex.object2d.Rectangle;
/**
 * Additively Weighted Voronoi Diagram algorithm
 * 
 * Reference: Okabe, Atsuyuki, Barry Boots, Kokichi Sugihara, and Sung Nok Chiu.
 * Spatial tessellations: concepts and applications of Voronoi diagrams. Vol.
 * 501. Wiley, 2009.
 * 
 * Original Code: https://github.com/MoritzStefaner/voitree
 * 
 * Modified on 07/05/2013 to make it suitable for my program
 * 
 * @author ZengWei
 * 
 */
public class OkabeVoronoi {
	private final float DWIDTH = 500;
	private float scale, dheight;
	float minX, minY, maxX, maxY;

	List<OkabeVoronoiCell> generators;

	public OkabeVoronoi(float minX, float minY, float maxX, float maxY) {
		this.minX = minX;
		this.minY = minY;
		this.maxX = maxX;
		this.maxY = maxY;

		scale = DWIDTH / (maxX - minX);
		dheight = (maxY - minY) * scale;

		generators = new ArrayList<OkabeVoronoiCell>();
	}

	public OkabeVoronoi(int width, int height) {
		this(0, 0, width, height);
	}

	public void setGenerators(List<OkabeVoronoiCell> generators) {
		this.generators = generators;
	}

	public List<OkabeVoronoiCell> generators() {
		return generators;
	}

	public void generate() {
		for (int i = 0; i < generators.size(); i++)
			generators.get(i).resetEdgeVertices();

		// Sort generators, lowest weight first
		Collections.sort(generators, new Comparator<OkabeVoronoiCell>() {
			@Override
			public int compare(OkabeVoronoiCell a, OkabeVoronoiCell b) {
				if (a.getWeight() == b.getWeight())
					return 0;
				if (a.getWeight() < b.getWeight())
					return -1;
				else
					return 1;
			}
		});

		// Consider bisector of i and j.
		// Regarding to Additively weighted Voronoi diagram, bisectors are
		// hyperbolic arc, that is, difference of two distances is constant. Two
		// distances are distance to i and distance to j.
		for (int i = 0; i < generators.size() - 1; i++) {
			for (int j = i + 1; j < generators.size(); j++) {
				// At first, rotate i and j such that two y-coordinates are
				// same. Next, move two points such that middle point of i and j
				// become origin point. That is, i and j become two foci as
				// (-a,0) and (a,0).
				// Compute hyperbolic arc (x,y) for (-a,0), (a,0) and rotate
				// back, move back.
				// Regarding to parameters, see Okabe, Boots, Sugihara, Chiu.
				// Spatial Tessellations, Wiley.
				OkabeVoronoiCell originalA = generators.get(i);
				OkabeVoronoiCell originalB = generators.get(j);

				float normalizedAX = (originalA.getX() - minX) / (maxX - minX)
						* DWIDTH;
				float normalizedAY = (originalA.getY() - minY) / (maxY - minY)
						* dheight;
				float normalizedAW = originalA.getWeight() * scale;
				OkabeVoronoiCell a = new OkabeVoronoiCell(normalizedAX, normalizedAY,
						normalizedAW);

				float normalizedBX = (originalB.getX() - minX) / (maxX - minX)
						* DWIDTH;
				float normalizedBY = (originalB.getY() - minY) / (maxY - minY)
						* dheight;
				float normalizedBW = originalB.getWeight() * scale;
				OkabeVoronoiCell b = new OkabeVoronoiCell(normalizedBX, normalizedBY,
						normalizedBW);

				float distAB = a.distanceTo(b);
				float abWeightDif = (b.getWeight() - a.getWeight());
				if (distAB > abWeightDif) {
					float distABh = distAB / 2;

					Point2D abCenter = a.getCenter().getPointAt(b.getCenter(),
							0.5f);
					float yyaw = abCenter.getY() - a.getY();
					float phaw = yyaw / distABh;
					float thaw = (float) Math.atan(phaw
							/ (float) Math.pow(1 - phaw * phaw, 0.5f));
					if (a.getX() < b.getX())
						thaw = (float) (Math.PI - (float) Math.atan(phaw
								/ (float) Math.pow(1 - phaw * phaw, 0.5f)));

					int minyawI = (int) -dheight;// (int)(minyaw+0.5);
					int maxyawI = (int) dheight;// (int)(maxyaw+0.5);
					// y loop
					for (int yjawI = minyawI; yjawI <= maxyawI; yjawI += 1) {
						float b1yaw = 4
								* (float) Math.pow(distABh * abWeightDif, 2)
								+ 4 * (float) Math.pow(abWeightDif * yjawI, 2)
								- (float) Math.pow(abWeightDif, 4);
						float b2yaw = 1 / (16 * distABh * distABh - 4
								* abWeightDif * abWeightDif);
						float b3yaw = b1yaw * b2yaw;
						if (b3yaw >= 0) {
							float x0aw = (float) Math.pow(b3yaw, 0.5f);
							float x10aw = abCenter.getX()
									+ (float) Math.cos(-thaw) * x0aw
									- (float) Math.sin(-thaw) * yjawI;
							float y10aw = abCenter.getY()
									+ (float) Math.sin(-thaw) * x0aw
									+ (float) Math.cos(-thaw) * yjawI;
							if (x10aw > 0 && x10aw < DWIDTH && y10aw > 0
									&& y10aw < dheight) {
								float d5aw = (float) Math.pow(
										(float) Math.pow(x10aw - a.getX(), 2)
												+ (float) Math.pow(
														y10aw - a.getY(), 2),
										0.5f)
										- a.getWeight();
								int br3aw = 0;
								for (int k = 0; k < generators.size(); k++) {
									OkabeVoronoiCell originalC = generators.get(k);

									float normalizedCX = (originalC.getX() - minX)
											/ (maxX - minX) * DWIDTH;
									float normalizedCY = (originalC.getY() - minY)
											/ (maxY - minY) * dheight;
									float normalizedCW = originalC.getWeight()
											* scale;

									OkabeVoronoiCell c = new OkabeVoronoiCell(
											normalizedCX, normalizedCY,
											normalizedCW);
									if (k != i && k != j) {
										float d6aw = (float) Math
												.pow((float) Math.pow(
														x10aw - c.getX(), 2)
														+ (float) Math.pow(
																y10aw
																		- c.getY(),
																2), 0.5f)
												- c.getWeight();
										if (d5aw > d6aw) {
											br3aw = 1;
											break;
										}// if d5aw>d6aw
									}// if kaw!=iaw
								}// next kaw
								if (br3aw == 0) {
									originalA.addVertice(new Point2D(x10aw,
											y10aw));
									originalB.addVertice(new Point2D(x10aw,
											y10aw));
								}// if br3==0
							}// if x10aw>0...
						}// if b3yaw>=0
					}// next yjawI
				}// if alaw>beaw
			}// next jmw
		}// next imw

		for (int i = 0; i < generators.size(); i++)
			generators.get(i).normalizeVertices(minX, minY, maxX, maxY, DWIDTH,
					dheight);
	}

	// private void evaluateX(){
	// float minyaw = 0;
	// float maxyaw = 0;
	// int rraw = 0;
	// int xjaw = 0;// x-coordinate
	// float a2raw = 0.5f / abWeightDif;
	// Point2D rotated = new Point2D();
	// while (rraw == 0) {
	// float a1raw = 16 * distABh * distABh * xjaw * xjaw - 4
	// * abWeightDif * abWeightDif * xjaw * xjaw - 4
	// * distABh * distABh * abWeightDif * abWeightDif
	// + (float) Math.pow(abWeightDif, 4);
	// if (a1raw >= 0) {
	// float yraw = a2raw * (float) Math.pow(a1raw, 0.5f);
	// float ymraw = -yraw;// y-coordinate
	// // move back and rotate back
	// rotated.setX(abCenter.getX()
	// + (float) Math.cos(-thaw) * xjaw
	// - (float) Math.sin(-thaw) * ymraw);
	// rotated.setY(abCenter.getY()
	// + (float) Math.sin(-thaw) * xjaw
	// + (float) Math.cos(-thaw) * ymraw);
	// // inside the screen
	// if (rotated.getX() > 0 && rotated.getX() < DWIDTH
	// && rotated.getY() > 0
	// && rotated.getY() < dheight) {
	// float d3aw = rotated.distance(a.getCenter())
	// - a.getWeight();
	// int br2aw = 0;
	// for (int k = 0; k < generators.size(); k++) {
	// AWVoronoiCell originalC = generators.get(k);
	//
	// float normalizedCX = (originalC.getX() - minX)
	// / (maxX - minX) * DWIDTH;
	// float normalizedCY = (originalC.getY() - minY)
	// / (maxY - minY) * dheight;
	// float normalizedCW = originalC.getWeight()
	// * scale;
	//
	// AWVoronoiCell c = new AWVoronoiCell(
	// normalizedCX, normalizedCY,
	// normalizedCW);
	//
	// if (k != i && k != j) {
	// float d4aw = rotated.distance(c
	// .getCenter()) - c.getWeight();
	// if (d3aw > d4aw) {// if k is closer,
	// // (x,y) is not
	// // bisector.
	// br2aw = 1;
	// break;
	// }// if d3aw>d4aw
	// }// if kaw!=iaw...
	// }// next kaw
	// if (br2aw == 0) {// All k is not closer than i,
	// // so (x,y) is bisector.
	// originalA.addVertice(new Point2D(rotated
	// .getX(), rotated.getY()));
	// originalB.addVertice(new Point2D(rotated
	// .getX(), rotated.getY()));
	// }// if br2aw==0
	// if (ymraw < minyaw)
	// minyaw = ymraw;
	// if (ymraw > maxyaw)
	// maxyaw = ymraw;
	// }// if x2raw>0 && ....1950
	// }// if a1raw>=0 1950
	// xjaw += 2;// next x
	// MBTools.debug(
	// "xjaw " + xjaw + " rotated "
	// + rotated.toString() + " a: "
	// + a.toString() + " b: " + b.toString()+" a1raw: "+a1raw,
	// true);
	// if (rotated.getX() < 0 || rotated.getX() > DWIDTH
	// || rotated.getY() < 0
	// || rotated.getY() > dheight)
	// rraw = 1;
	//
	// if (xjaw < 100)
	// rraw = 0;
	// }// while rraw==0
	// }

	public float[] getBoundCoords() {
		float[] bound = { minX, minY, maxX, maxY };
		return bound;
	}

	public Rectangle getBound() {
		return new Rectangle(minX, minY, maxX, maxY);
	}
}
